package com.zwy.leetcode;

import java.util.*;

public class DPTest {
    /**
     * 爬楼梯
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        int []dp=new int[n+1];
        if(n==1)return 1;
        if(n==2)return 2;
        dp[1]=1;
        dp[2]=2;
        for (int i = 3; i <=n ; i++) {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }

    /**
     *买卖股票的最佳时机
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int []sell=new int[prices.length-1];
        int length=prices.length;
        int max=prices[length-1];
        sell[length-2]=max;
        for (int i = length-3; i >=1; i--) {
            if(prices[i]>max)
                max=prices[i];
            sell[i]=max;
        }

        return 0;
    }



    /**
     *打家劫舍
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        if(nums.length==0)return 0;
        if(nums.length==1)return nums[0];
        int []dp=new int[nums.length];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        int max=Math.max(dp[nums.length-1],dp[nums.length-2]);
       return max;
    }

    /**
     * 换零钱
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {
        int []dp=new int[amount+1];
        int min=0;
        for (int i = 1; i <amount+1 ; i++) {
            dp[i]=amount+1;
        }
        for (int i = 0; i < dp.length; i++) {
            min=amount+1;
            dp[0]=0;
            for (int j = 0; j < coins.length; j++) {
                if(i>=coins[j]) {
                    dp[i] = 1 + dp[i - coins[j]];
                    dp[i] = Math.min(min, dp[i]);
                    min=dp[i];
                }
            }

        }
       return dp[amount]>amount?-1:dp[amount];
    }

    /**
     * 无重复字符的最长子串
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        if(s.length()==0)return 0;
        Set<Character>set=new HashSet<Character>();
        int start=0;
        int count=1;
        int max=1;
        set.add(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
           while(set.contains(s.charAt(i))){
                count--;
                start++;
                set.clear();
                for (int j = start; j <start+count ; j++) {
                    set.add(s.charAt(j));
                }
            }
           set.add(s.charAt(i));
           count++;
           max=Math.max(max,count);
        }
        return max;
    }


    /**
     *  删除并获得点数
     * @param nums
     * @return
     */
    public int deleteAndEarn(int[] nums) {
        int max=0;
        int count=0;
        for (int i = 0; i <nums.length ; i++) {
            count=nums[i];
            if((nums[i]-1)>=0&&(nums[i]-1)<nums.length&&(nums[i]-1)!=i)
                count+=nums[nums[i]-1];
            if((nums[i]+1<nums.length)&&(nums[i]+1)!=i)
                count+=nums[nums[i]+1];
            max=Math.max(max,count);
        }
        return max;
    }

    /**
     * 跳跃游戏
     * @param nums
     * @return
     */
    public boolean canJump(int[] nums) {
        if(nums.length<2)return true;
        int []dp=new int[nums.length];
        int max=nums[0];
        dp[0]=nums[0];
        for (int i = 1; i < dp.length-1; i++) {
            if(max>=i){
                dp[i]=i+nums[i];
            }
            max=Math.max(max,dp[i]);
        }
        return max>=dp.length-1?true:false;
    }

    /**
     * 跳跃游戏 II
     * @param nums
     * @return
     */
    public int jump(int[] nums) {
        if(nums.length<2)return 0;
        int []dp=new int[nums.length];
        dp[0]=0;
        for (int i = 1; i < dp.length; i++) {
            int t=nums.length;
            int min=nums.length;
            for (int j = 0; j < i; j++) {
                if(j+nums[j]>=i){
                    t=dp[j]+1;
                }
                min=Math.min(t,min);
            }
            dp[i]=min;
        }
        return dp[dp.length-1];
    }

    /**
     * 最大子序和
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        if(nums.length==0)return 0;
        if(nums.length==1)return nums[0];
        int []dp=new int[nums.length];
        int max=nums[0];
        dp[0]=nums[0];
        for (int i = 1; i < dp.length; i++) {
            if(dp[i-1]>0)
                dp[i]=dp[i-1]+nums[i];
            else
                dp[i]=nums[i];
            max=Math.max(max,dp[i]);
        }
        return max;
    }

    /**
     *  环形子数组的最大和
     * @param nums
     * @return
     */
    public int maxSubarraySumCircular(int[] nums) {
        if(nums.length==0)return 0;
        if(nums.length==1)return nums[0];
        int sum=0;
        int []dp=new int[nums.length];
        int []dp2=new int[nums.length];
        int min=0;
        int max=nums[0];
        dp[0]=nums[0];
        sum=nums[0];
        for (int i = 1; i < dp.length; i++) {
            sum+=nums[i];
            if(dp[i-1]>0)
                dp[i]=dp[i-1]+nums[i];
            else
                dp[i]=nums[i];
            max=Math.max(max,dp[i]);
        }
        dp2[0]=nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp2[i]=nums[i]+Math.min(0,dp2[i-1]);
            min=Math.min(min,dp2[i]);
        }
        if(sum==min)return max;
        return sum-min>max?sum-min:max;
    }

    /**
     * 乘积最大子数组
     * @param nums
     * @return
     */
    public int maxProduct(int[] nums) {
        return 0;
    }

    public static void main(String[] args) {
      String s="abcabcbb";
        DPTest test=new DPTest();
        int i = test.lengthOfLongestSubstring(s);
        System.out.println(i);
    }
}
